//非递归版本二叉搜索树
#include<iostream>
#include<stack>
using namespace std;


template<class K,class V>
struct BSTreeNode
{
    BSTreeNode<K,V>* left;
    BSTreeNode<K,V>* right;
    pair<K,V> _kv;
    BSTreeNode(const pair<K,V>& v)
        :left(nullptr),right(nullptr),_kv(v)
    {}
};

template<class K,class V>
class BSTree
{
public:
    typedef BSTreeNode<K,V> Node;
    BSTree()
    {
        root = nullptr;
    }
    Node* find(const K& key)
    {
        if(root == nullptr)
            return nullptr;
        Node* cur = root;
        while(cur)
        {
            if(cur->_kv.first > key)
                cur = cur->left;
            else if(cur->_kv.first < key)
                cur = cur->right;
            else
                return cur;
        }
        return nullptr;
    }
    bool insert(const pair<K,V>& kv)
    {
        if(find(kv.first)) //数据冗余
            return false;
        if(root == nullptr)
        {
            root = new Node(kv);
            return true;
        }
        Node* cur = root;
        Node* parent = nullptr;
        while(cur)
        {
            if(cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->left;
            }
            else if(cur->_kv.first < kv.first)
            {
                parent = cur;
                cur = cur->right;
            }
            else
                return false;
        }
        cur = new Node(kv);
        if(parent->_kv.first > kv.first)
            parent->left = cur;
        else
            parent->right = cur;
        return true;   
    }
    bool erase(const K& key)
    {
        if(find(key) == nullptr)
        {
            return false;
        }
        Node* cur = root;
        Node* parent = nullptr;
        while(cur)
        {
            if(cur->_kv.first > key)
            {
                parent = cur;
                cur = cur->left;
            }
            else if(cur->_kv.first < key)
            {
                parent = cur;
                cur = cur->right;
            }
            else //找到了
            {
                //case1:只有一个孩子
                if(cur->left == nullptr)
                {
                    if(parent == nullptr)
                    {
                        root = root->right;
                    }
                    else
                    {
                        if(parent->left == cur)
                        {
                            parent->left = cur->right;
                        }
                        else
                        {
                            parent->right = cur->right;
                        }
                    }
                    delete cur;
                }
                else if(cur->right == nullptr)
                {
                    if(parent == nullptr)
                    {
                        root = root->left;
                    }
                    else
                    {
                        if(parent->left == cur)
                        {
                            parent->left = cur->left;
                        }
                        else
                        {
                            parent->right = cur->left;
                        }
                    }
                    delete cur;
                }
                else //左右孩子双全
                {
                    //替换删除法：找左树最右节点删除
                    Node* minParent = cur;
                    Node* min = cur->left;
                    while(min->right)
                    {
                        minParent = min;
                        min = min->right;
                    }
                    swap(cur->_kv,min->_kv);
                    if(minParent->left == min) //min是没有右孩子了
                        minParent->left = min->left;
                    else
                        minParent->right = min->left;

                    delete min;
                }
                return true;
            }
        }
        return false;   
    }
    K& GetRootVal()
    {
        return root->_kv.first;
    }
    void inorder()
    {
        _inorder(root);
        cout << endl;
    }
    void _inorder(Node* root)
    {
        if(root == nullptr)
            return ;
        _inorder(root->left);
        cout << root->_kv.first<<" ";
        _inorder(root->right);
    }
    void inorderNon()
    {
        stack<Node*> st;
        Node* cur = root;
        while(!st.empty() || cur)
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            Node* top = st.top();
            st.pop();
            cout << top->_kv.first <<" ";

            cur = top->right;
        }
        cout << endl;
    }
private:
    BSTreeNode<K,V>* root;
};
